package main

import "fmt"

// main
//
//	@Description: 二叉树三种遍历：前序、中序、后序 都是指的根节点遍历的时机  详见binarytree.png
//
// 前序：先输出根节点，再输出左子树，最后输出右子树
// 中序：先输出左子树，再输出根节点，最后输出右子树
// 后序：先输出左子树，再输出右子树，最后输出根节点
func main() {
	root := &TreeNode{
		No:   1,
		Name: "宋江",
	}
	lef1 := &TreeNode{
		No:   2,
		Name: "吴用",
	}

	right1 := &TreeNode{
		No:   3,
		Name: "卢俊义",
	}
	root.Left = lef1
	root.Right = right1

	right2 := &TreeNode{
		No:   4,
		Name: "林冲",
	}
	right1.Right = right2

	lef2 := &TreeNode{
		No:   10,
		Name: "吴用10",
	}
	lef1.Left = lef2
	lef3 := &TreeNode{
		No:   12,
		Name: "吴用12",
	}
	lef1.Right = lef3

	//前序
	//PreOrder(root)

	//中序遍历
	//InFixOrder(root)
	//后续遍历
	PostOrder(root)
}

// PreOrder
// no=1 name=宋江
// no=2 name=吴用
// no=10 name=吴用10
// no=12 name=吴用12
// no=3 name=卢俊义
// no=4 name=林冲
//
//	@Description: 前序遍历：先输出根节点，再输出左子树，最后输出右子树
//	@param t
func PreOrder(node *TreeNode) {
	if node != nil {
		fmt.Printf("no=%d name=%v \n", node.No, node.Name)
		PreOrder(node.Left)
		PreOrder(node.Right)
	}
}

// InFixOrder
// no=10 name=吴用10
// no=2 name=吴用
// no=12 name=吴用12
// no=1 name=宋江
// no=3 name=卢俊义
// no=4 name=林冲
//
//	@Description: 中序遍历
//	@param node
func InFixOrder(node *TreeNode) {
	if node != nil {
		InFixOrder(node.Left)
		fmt.Printf("no=%d name=%v \n", node.No, node.Name)
		InFixOrder(node.Right)
	}
}

// PostOrder
// no=10 name=吴用10
// no=12 name=吴用12
// no=2 name=吴用
// no=4 name=林冲
// no=3 name=卢俊义
// no=1 name=宋江
//
//	@Description: 后续
//	@param node
func PostOrder(node *TreeNode) {
	if node != nil {
		PostOrder(node.Left)
		PostOrder(node.Right)
		fmt.Printf("no=%d name=%v \n", node.No, node.Name)
	}
}

type TreeNode struct {
	No    int
	Name  string
	Left  *TreeNode
	Right *TreeNode
}
